#include <stdio.h>
#include "algo_mergeSort.h"
#include "algo_findIntersection.h"

#define size1 10
#define size2 15
#define size3 3
 
// an implementation of binary search using recursive approach
// return the index of array where num is found  (-1 -> not found)
int binarySearch_recursive(int a[], int num, int start, int end) {
	if (end < start)
		return -1;
	int mid = (start + end)/2;
	if (a[mid] > num) 
		return binarySearch_recursive(a, num, start, mid-1);
	else if (a[mid] < num) 
		return binarySearch_recursive(a, num, mid+1, end);
	else
		return mid;
}

// an implementation of binary search using iterative approach
// return the index of array where num is found  (-1 -> not found)
int binarySearch_iterative(int a[], int num, int start, int end) {
	int mid = (start + end)/2;;
	while ((a[mid] != num) && start <= end) {
		mid = (start + end)/2;
		if (num > a[mid])
			start = mid + 1;
		else
			end = mid - 1;
	} 
	if (a[mid] == num)    
		return mid;
	else 
	    return -1;
}

void findIntersection_largearray(int smallArray[], int largeArray[], int length_small, int length_large) {
	// loop for all numbers in a small array
	for (int i = 0; i < length_small; i++) {
		// perform binary on the large array
		if (binarySearch_iterative(largeArray, smallArray[i], 0, length_large) != -1)
			printf("%d ", smallArray[i]);		
	}
	printf("\n");
}

void findIntersection(int a[], int b[], int length1, int length2) {
    int index1, index2;
	index1 = index2 = 0;
	while (index1 < length1 && index2 < length2) {
		if (a[index1] < b[index2])
			index1++;
		else if (a[index1] > b[index2])
			index2++;
		else {
			printf("%d ", a[index1]);
			index1++;
			index2++;
		}		
	}
	printf("\n");
}

void test_algo_findIntersection() {
	int array1[] = { 12, 1, 3, 28, 9, 8, 2, 7, 10, 15 };
	int array2[] = { 20, 5, 3, 15, 22, 26, 28, 30, 2, 8, 11, 10, 12, 9, 16 };
	int array3[] = { 11, 2, 1 };
	
	mergeSort(array1, 0, size1-1);
	printf("Array 1:\n");
	for (int i = 0; i < size1; i++) {
		printf("%d", array1[i]);
		if ( i < size1 - 1 )
			printf(", ");
		else
			printf("\n");
	}
	mergeSort(array2, 0, size2-1);
	printf("Array 2:\n");
	for (int i = 0; i < size2; i++) {
		printf("%d", array2[i]);
		if ( i < size2 - 1 )
			printf(", ");
		else
			printf("\n");
	}
	printf("\n");

	mergeSort(array3, 0, size3-1);
	printf("Array 3:\n");
	for (int i = 0; i < size3; i++) {
		printf("%d", array3[i]);
		if ( i < size3 - 1 )
			printf(", ");
		else
			printf("\n");
	}
	printf("\n");

	printf("Intersection of array1 and array2: \n");
	findIntersection(array1, array2, size1, size2);

    printf("Intersection of array3 and array2 (large array method): \n");
	findIntersection_largearray(array3, array2, size3, size2);
}
